package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/
 * @create 2025/9/11 20:18
 * @since JDK17
 */

public class Solution100 {
    int m, n;
    char[][] g;
    boolean[][][] vis;
    boolean dfs(int x, int y, int c) {  // c : 平衡度
        if (c > m + n - x - y - 1) {
            return false;
        }
        if (x == n - 1 && y == m - 1) {
            return c == 1;
        }
        if (vis[x][y][c]) {
            return false;
        }
        vis[x][y][c] = true;
        c += g[x][y] == '(' ? 1 : -1;
        return c >= 0 && (x < n - 1 && dfs(x + 1, y, c) || y + 1 < m && dfs(x, y + 1, c));
    }

    public boolean hasValidPath(char[][] grid) {
        g = grid;
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m][(m + n + 1) / 2];
        if (g[0][0] == ')' || g[n - 1][m - 1] == '(' || (m + n) % 2 == 0) {
            return false;
        }
        return dfs(0, 0, 0);
    }
}
